Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Heute fangen wir jetzt ein neues Thema an, auch ein Klassiker sozusagen der kombinatorischen Optimierung.

Das sind nämlich maximale Flüsse und deren Charakterisierung über minimale Schnitte.

Das ist, wenn man so möchte, einer der Anfänge in der kombinatorischen Optimierung,

gehört zu den klassischen Resultaten der kombinatorischen Optimierung.

Das Ergebnis werden wir heute auch sehen und auch beweisen und daraus ableitend auch Algorithmen kennenlernen,

die dann, wie man schon mal kennenlernt, in der Grundversion erstmal nicht polynomial funktionieren.

Also nochmal die Erinnerung an gestern, wenn da irgendein C, also irgendein Datum aus dem Input,

als Zahl in der Laufzeit auftaucht, ist es exponentiell.

Und so wird das bei der Grundversion auch sein bei maximalen Flüssen,

aber dann werden wir sehen, wie wir das loswerden.

Wir kommen tatsächlich zu polynomialen, sprich sogar streng polynomialen Algorithmen.

Da werden wir uns zwei von denen genauer ansehen.

Gibt es da erstmal bis dahin noch Fragen zum zu kürzesten Mägen und zu gestern?

Gut, also dann gucken wir uns das neue Kapitel an, das ist Kapitel 8, maximale Flüsse.

Und ich fange einfach erstmal mit einer Definition an und dann schauen wir, wo das vorkommt und was das für einen Sinn macht,

sozusagen die Definition. Also wir haben wieder ein D-Graphen, V,a.

Und wir haben wieder Gewichte und diesmal sind es keine Gewichte in dem Sinne von einer Zielfunktion,

sondern Kapazitäten auf den Kanten. Bogenkapazitäten, wir nennen die Bogenkapazitäten C von A,

die sind alle größer als Null, Kapazitäten negativ, macht wenig Sinn.

Und wir haben wieder zwei Knoten, sein S und T aus V nicht dieselben und S heißt Quelle und T heißt Senke.

Also immer die Abkürzungen kommen nicht aus dem Deutschen, sondern aus dem Englischen.

S im Englischen für Source und T im Englischen für Target, daher das S und das T.

So, jetzt nennen wir eine Funktion X, die geht von den Kanten nach R, heißt zulässiger Fluss.

Falls zwei Bedingungen erfüllt sind. Die erste Bedingung ist die Kapazitätsbedingung,

falls erstens das X immer zwischen Null und den Kapazitäten ist, also für alle A aus A,

das nennt man die Kapazitätsbedingung oder?

Und die zweite Bedingung nennt man Flusserhaltungsbedingung.

Ich schaue mir an, alles was in den Knoten reingeht von Werten muss dasselbe sein wie das was rausgeht.

Und das für alle V aus V und diese Bedingung heißt Flusserhaltung.

Also als Beispiel, ich schaue mir einfach von einem Knoten V an alle Werte die hier irgendwie reingehen.

1, 3, 17, das muss genau der Summe entsprechen die die rausgeht, zum Beispiel 10, 11, das heißt Flusserhaltung.

Also ich schicke sozusagen was in einen Knoten rein und in dem Knoten selber geht nichts verloren.

Deswegen ein Stück weit Fluss, also wenn man fast diese X-Werte als Flüsse aufstellen sich ein Rohrleitungssystem vor.

Das sind Rohre, da fließt sozusagen, fließen irgendwelche Einheiten, Flüsse, Wasser, Gas, was auch immer.

Und alles was sich in eine Verzweigung reingeht, geht auch wieder raus. Also geht unterwegs nichts verloren.

Keine Lex sozusagen oder Autoverkehr. 21 Autos kommen an eine Kreuzung, die verlassen auch wieder alle 21.

Da verschwindet keiner im Kuli.

Das heißt, wenn du die aus der Quelle rauskommst, dann muss man auch in der Senke ankommen.

Genau, das ist das was wir jetzt gleich als erstes sehen.

Also das sollte man hier, das stimmt, gut dass Sie das sagen, also und V ungleich S und T.

Also die beiden nehmen wir aus. Wir können sie mit der gleichen Transformation auch reinnehmen,

aber die klassische Formulierung erstmal, dass man die beiden rausnimmt.

Und wie Sie gerade schon recht richtig feststellen, wenn unterwegs nichts verloren geht,

alles was man vorne rein schickt, sollte hinten rauskommen.

Und das Ziel ist genau, die Frage ist, wie viel kann ich denn reinschicken, dass auch hinten ankommt.

Und das nennt man den Wertenfluss des Flusses.

Also wenn x zulässig ist, man schreibt dann auch gern zulässiger St-Fluss,

also um das S und das T noch zu spezifizieren, vielleicht sollte ich das hier ergänzen.

Ja, wenn es im Kontext klar ist, lässt man es gerne weg, weil Mathematiker schreibfall sind,